1. Field of the Invention
The present invention is related to computer networks, and more particularly to a system and method for partitioning a routing information base among two or more processors.
2. Background Information
A network protocol is a set of rules defining how nodes in a network interact with each other. A routing protocol is a network protocol whose purpose is to compute routes or paths through the network according to some algorithm, in order to enable routers in a network to forward data packets towards their destinations. The term “routing protocol” is also used to indicate software which implements a routing protocol; this is the sense in which we use the term.
A Routing Information Base (RIB) stores routes associated with one or more protocols. In one approach, the Routing Information Base (RIB) is implemented with a type of binary tree called a radix trie. Other data structures can be used as well.
In a traditional routing system, protocol-based RIBs download all or some of their routing information to a global RIB. To date, all RIBs have been stored on a single processor. Such an approach means that routing information can be retrieved from a single location. At the same time, however, the address space of the processor limits the total number of routes that can be stored. This limit places constraints on the number of connections that can be handled by a router. What is needed is a system and method of increasing the size of the routing information base beyond the address space limitations of individual processors.
This limitation also leaves the RIB processor bound. That is, even if the processor can address all possible routes, the computational power of the processor may be limited such that it is unable to perform operations on the routes, such as selection of the best route, or to serve the routes up in a timely manner. What is needed, therefore, is a system and method for distributing a routing information base across two or more processors.